package Week7.J0527;


import java.util.ArrayList;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}

// 注意重写comparable接口！
public class 合并k个已排序的链表_xv {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((l1, l2) -> {
            return l1.val - l2.val;
        });
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                heap.offer(lists.get(i));
            }
        }

        ListNode ret = new ListNode(0); // 创建虚拟头节点
        ListNode prev = ret; // 创建指针指向ret
        while (!heap.isEmpty()) {
            ListNode t = heap.poll();
            prev.next = t; // 把 t 接上 ret
            prev = prev.next; // 更新指针
            if (t.next != null) heap.offer(t.next);
        }

        return ret.next;
    }
}
